import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 139.单词拆分
 */
public class Exerciser7 {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 优化，把字典的单词放入 哈希表中，方便寻找
        Set<String> hash = new HashSet<>(wordDict);
        // dp[i]表示: 从0到i位置的字符，能否被字典中的单词拼接而成
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        // 初始化：，不能影响后续的结果
        dp[0] = true;
        s = " " + s;//把s进行整体后移一位，进行重新初始化，方便后续进行操作
        for(int i = 1;i <= n;i++) {
            for(int j = i;j >= 1;j--) {
                if(dp[j - 1] && hash.contains(s.substring(j,i + 1))) {
                    // 左闭右开所以是i+1
                    // 把0-i分成两份，一份是0-j-1，另一份是j-i，
                    // 前一份是dp值为true，说明可以拼接而成
                    // 后一份是s中的字符剩下的在字典中可以找到，这样说明是0-i位置的字符串是可以在字典的单词拼接而成的
                    dp[i] = true;
                    break; //找到直接返回，去寻找下一个位置
                }
            }
        }
        return dp[n];
    }
}
